package hot100.logos11To20;

import java.util.ArrayList;
import java.util.List;

/**
 * @author logos
 * date 2025/7/12 10:30
 * @version v1.0
 * @Package hot100
 */
public class logos19 {


    /**
     * 19. 螺旋矩阵
     * https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public static final int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

        public static final int INF = -101;

        public List<Integer> spiralOrder(int[][] matrix) {
            int n = matrix.length;
            int m = matrix[0].length;
            List<Integer> ans = new ArrayList<>(n * m);
            for (int i = 0, x = 0, y = 0, d = 0; i < n * m; i++) {
                ans.add(matrix[x][y]);
                matrix[x][y] = INF;
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m || matrix[nx][ny] == INF) {
                    d = (d + 1) % 4;
                    nx = x + dirs[d][0];
                    ny = y + dirs[d][1];
                }
                x = nx;
                y = ny;
            }
            return ans;
        }
    }


}
